﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace TSP
{
    class Program
    {
        /*
        public static void Kruskal(AdjacencyMatrixGraph graph)
        {
            //kruskal
            AdjacencyMatrixGraph g2 = (AdjacencyMatrixGraph)graph.KruskalMST();
            Console.WriteLine("Created minimal spenning tree: ");
            show(g2);
        }
         */

        // Krok 2
        private static List<Vertex> findOddVertexes(Graph graph)
        {
            List<Vertex> listOfOddVertex = new List<Vertex>();
            // Krok 1 - Find odd vertexes
            for (int i = 0; i < graph.verticesCount ; i++)
            {
                if ((graph.vertices[i].Neighbours.Count % 2) == 1)
                {
                    listOfOddVertex.Add(graph.vertices[i]);
                }
            }
            return listOfOddVertex;
        }

        // pomocnicza funkcja do Kroku 3
        // true = there are already this points in the edge list
        // false = there are not
        private static bool check_if_any_of_points_is_in_list(List<Edge> g_e, Vertex v, Vertex v2)
        {
            /*foreach (Edge e in g_e)
            {
                if (((e.From.Position.X == v.Position.X) && (e.From.Position.Y == v.Position.Y))//checknig of first point
                    && ((e.To.Position.X == v2.Position.X) && (e.To.Position.Y == v2.Position.Y)))//checking of second point
                {
                    return true;
                }
                // vice versa - pierwszy punkt sprawdzamy jako drugi
                if (((e.To.Position.X == v.Position.X) && (e.To.Position.Y == v.Position.Y))//checknig of first point
                    && ((e.From.Position.X == v2.Position.X) && (e.From.Position.Y == v2.Position.Y)))//checking of second point
                {
                    return true;
                }
            }
            return false;*/

            // POPRAWIONE - dla MATCHINGU:
            foreach (Edge e in g_e)
            {
                if (((e.From.Position.X == v.Position.X) && (e.From.Position.Y == v.Position.Y))//checknig of first point
                    || ((e.To.Position.X == v2.Position.X) && (e.To.Position.Y == v2.Position.Y)))//checking of second point
                {
                    return true;
                }
                // vice versa - pierwszy punkt sprawdzamy jako drugi
                if (((e.To.Position.X == v.Position.X) && (e.To.Position.Y == v.Position.Y))//checknig of first point
                    && ((e.From.Position.X == v2.Position.X) && (e.From.Position.Y == v2.Position.Y)))//checking of second point
                {
                    return true;
                }
            }
            return false;

        }
        // pomocnicza do kroku 3 i 5
        private static bool this_vertex_exists_in_list(List<Vertex> g_v, Vertex v)
        {
            foreach (Vertex v_parent in g_v)
            {
                if ((v_parent.Position.X == v.Position.X) && (v_parent.Position.Y == v.Position.Y))//checknig of first point
                {
                    return true;
                }
            }
            return false;
        }

        // Krok 3
        private static Graph minimum_weight_matiching(List<Vertex> listOfOddVertex)
        {
            Graph g = new Graph();
            List<Vertex> g_v = new List<Vertex>();
            List<Edge> g_e = new List<Edge>();
            int number_of_added_vert = 0;
            foreach (Vertex v in listOfOddVertex)
            {
                Vertex best_vertex = null;
                double current_distance = 0;
                double best_distance = -1;
                bool at_least_one_edge_was_found = false;
                foreach (Vertex v2 in listOfOddVertex)
                {
                    //We check if they are the same => then we skip
                    if ((v.Position.X != v2.Position.X) && (v.Position.Y != v2.Position.Y))
                    {
                        //We check if either of points is already in final list of vertex'es: g_v
                        //if (!check_if_any_of_points_is_in_list(g_e, v, v2))
                        if ((!this_vertex_exists_in_list(g_v, v))&&(!this_vertex_exists_in_list(g_v, v2)))
                        {
                            current_distance = Math.Sqrt(Math.Pow(v2.Position.X - v.Position.X, 2) + Math.Pow(v2.Position.Y - v.Position.Y, 2));
                            if ((best_distance > current_distance) || (best_distance == -1))
                            {
                                best_distance = current_distance;
                                best_vertex = v2;
                                at_least_one_edge_was_found = true;
                            }
                        }
                        else
                        {
                            // they are both in this list => they already got best fit => we skip
                            // FIXED AFTER CORRECT MATCHING
                            //break;
                        }
                    }
                }
                if (at_least_one_edge_was_found)
                {
                    if (!this_vertex_exists_in_list(g_v, v))
                    {
                        g_v.Add(new Vertex(v));
                        number_of_added_vert++;
                    }
                    if (!this_vertex_exists_in_list(g_v, best_vertex))
                    {
                        g_v.Add(new Vertex(best_vertex));
                        number_of_added_vert++;
                    }
                    g_e.Add(new Edge(v, best_vertex, best_distance));
                }

            }
            g.edges = g_e;
            g.vertices = g_v;
            g.verticesCount = number_of_added_vert;
            return g;
        }
        // Funkcja pomocnicza do kroku 4a
        private static bool edge_present_in_graph(Graph mst, Edge edge_to_check)
        {
            foreach (Edge e in mst.edges)
            {
                if (((e.From.Position.X == edge_to_check.From.Position.X) && (e.From.Position.Y == edge_to_check.From.Position.Y))//checknig of first point
                    && ((e.To.Position.X == edge_to_check.To.Position.X) && (e.To.Position.Y == edge_to_check.To.Position.Y)))//checking of second point
                {
                    return true;
                }
                if (((e.From.Position.X == edge_to_check.To.Position.X) && (e.From.Position.Y == edge_to_check.To.Position.Y))//checknig of first point
                   && ((e.To.Position.X == edge_to_check.From.Position.X) && (e.To.Position.Y == edge_to_check.From.Position.Y)))//checking of second point
                {
                    return true;
                }
            }
            return false;
        }
        //Krok 4a
        private static Graph combine_mst_with_minweight_match_g(Graph mst, Graph min_weight_match_g)
        {
            foreach(Edge e in min_weight_match_g.edges)
            {
                //if (!edge_present_in_graph(mst, e))
                //{
                    mst.edges.Add(e);
                //}
            }
            return mst;
        }
        // Pomocnicza funkcja do 4b
        private static void findtour(ref Graph mst_with_mwmg, Vertex u, ref List<Vertex> euler_path)
        {
            //'tour' is a stack

            //find_tour(u):
            //    for each edge e=(u,v) in E:
            //        remove e from E
            //        find_tour(v)
            //    prepend u to tour

            //to find the tour, clear stack 'tour' and call find_tour(u),
            //where u is any vertex with a non-zero degree.
            foreach (Edge e in mst_with_mwmg.edges)
            {
                if (e.HasBeenUsedByEuler == false)
                {
                    // vertex == u
                    if ((u.Position.X == e.From.Position.X) && (u.Position.Y == e.From.Position.Y))
                    {
                        e.HasBeenUsedByEuler = true;
                        findtour(ref mst_with_mwmg, e.To, ref euler_path);
                    }
                    else if ((u.Position.X == e.To.Position.X) && (u.Position.Y == e.To.Position.Y))
                    {
                        e.HasBeenUsedByEuler = true;
                        findtour(ref mst_with_mwmg, e.From, ref euler_path);
                    }
                }
            }
            euler_path.Add(u);
        }
        // Krok 4b
        private static List<Vertex> find_euler_path(Graph mst_with_mwmg)
        {
            List<Vertex> euler_path = new List<Vertex>();
            findtour(ref mst_with_mwmg, mst_with_mwmg.vertices[0],ref euler_path);
            return euler_path;
        }
        // Krok 5
        private static List<Vertex> find_good_aprox_of_tsp(List<Vertex> euler_path)
        {
            List<Vertex> output = new List<Vertex>();
            foreach (Vertex v in euler_path)
            {
                if (!this_vertex_exists_in_list(output, v))
                {
                    output.Add(v);
                }
            }
            output.Add(euler_path[euler_path.Count-1]);//Dodanie ostatniego elementu
            return output;
        }

        private static double calculateDistance(List<Vertex> list)
        {
            double output = 0;

            Vertex from = null;
            Vertex to = null;
            for (int i = 0; i < list.Count-1; i++)
            {
                from = list.ElementAt(i);
                to = list.ElementAt(i + 1);
                foreach (Edge e in from.Neighbours)
                {
                    if (e.From == from && e.To == to)
                    {
                        output += e.Weight;
                    }
                }
                    
            }

            return output;
        }

        static void usage()
        {
            Console.WriteLine("USAGE: TSP.exe mode data");
            Console.WriteLine("mode:");
            Console.WriteLine("r - for random generated graph");
            Console.WriteLine("f - for loading graph from txt file");
            Console.WriteLine("data:");
            Console.WriteLine("with r: number of vertices to generate");
            Console.WriteLine("with f: absolute path to txt file with vertices");
            Console.WriteLine("File content:");
            Console.WriteLine("Each vetrex in separete line as <X,Y> , where X and Y are coordiantes in natural number.");
            Console.Read();
        }

        static void Main(string[] args)
        {
            if (args.Length != 2)
            {
                usage();
            }
            else
            {
                if (args[0] == "r")
                {
                    int n = Int32.Parse(args[1]) ;
                    if (n> 0 && n < 100)
                    {
                            runRandom(n);
                    }
                    else
                    {
                        usage();
                    }
                }
                else if (args[0] == "f")
                {
                    string filename = args[1];
                    String line;
                    List<Vertex> vertices = new List<Vertex>();
                    try
                    {
                        //Pass the file path and file name to the StreamReader constructor
                        StreamReader sr = new StreamReader(filename);

                        //Read the first line of text
                        line = sr.ReadLine();

                        //Continue to read until you reach end of file
                        while (line != null)
                        {
                            //write the lie to console window
                            int separator = line.IndexOf(',');
                            int end = line.IndexOf('>');
                            int x = Int32.Parse(line.Substring(1,separator - 1));
                            int y = Int32.Parse(line.Substring(separator+1,end-separator-1));
                            //Console.WriteLine(x+" , "+y);
                            vertices.Add(new Vertex(new System.Drawing.Point(x,y)));
                            //Read the next line
                            line = sr.ReadLine();
                        }

                        //close the file
                        sr.Close();
                        runFile(vertices);
                    }
                    catch (Exception e)
                    {
                        Console.WriteLine("Exception: " + e.Message);
                    } 
                }
                else
                {
                    usage();

                }
            }
        }

        static void runFile(List<Vertex> vertices)
        {
            try
            {
                //tworzenie grafu
                Graph g = new Graph(vertices);
                //print grafu
                Console.WriteLine("Graph created: ");
                Console.WriteLine(Graph.print(g));
                //Console.WriteLine(Graph.printEdges(g));

                //kruskal
                // Krok 1 - Kruskal - Find Minimum Spanning Tree
                Graph mst = g.kruskalMST(g);/*
                Console.WriteLine("After Kruskal's algorithm:");
                Console.WriteLine(Graph.print(mst));
                Console.WriteLine(Graph.printEdges(mst));
                */

                // Krok 2 - Find odd vertexes
                List<Vertex> listOfOddVertex = findOddVertexes(mst);
                // Krok 3 - MinmumWeight Matching of odd vertexes
                Graph min_weight_match_g = minimum_weight_matiching(listOfOddVertex);
                // Krok 4a - Połączenie MST z min_weight_match_g
                Graph mst_with_mwmg = combine_mst_with_minweight_match_g(mst, min_weight_match_g); // byc moze do poprawy - wiecej debugow
                // Krok 4b - Find Euler Cycle Path
                List<Vertex> euler_path = find_euler_path(mst_with_mwmg);
                // Krok 5 - Find TSP Cycle Path using Shortcut concept
                List<Vertex> tsp_path = find_good_aprox_of_tsp(euler_path);
                double distance = calculateDistance(tsp_path);
                Console.WriteLine("Order of vertices:");
                foreach (Vertex v in tsp_path)
                {
                    Console.Write("<" + v.Position.X + "," + v.Position.Y + ">, ");
                }
                Console.WriteLine("distance: {0:0.0000}", distance);
                Console.Read();

            }
            catch (ArgumentException aex)
            {
                Console.WriteLine(aex.Message);
            }
        }

        static void runRandom(int n)
        {
            try
            {
                    //tworzenie grafu
                    Graph g = new Graph(n);
                    //print grafu
                    Console.WriteLine("Graph created: ");
                    Console.WriteLine(Graph.print(g));
                    //Console.WriteLine(Graph.printEdges(g));

                    //kruskal
                    // Krok 1 - Kruskal - Find Minimum Spanning Tree
                    Graph mst = g.kruskalMST(g);/*
                Console.WriteLine("After Kruskal's algorithm:");
                Console.WriteLine(Graph.print(mst));
                Console.WriteLine(Graph.printEdges(mst));
                */

                    // Krok 2 - Find odd vertexes
                    List<Vertex> listOfOddVertex = findOddVertexes(mst);
                    // Krok 3 - MinmumWeight Matching of odd vertexes
                    Graph min_weight_match_g = minimum_weight_matiching(listOfOddVertex);
                    // Krok 4a - Połączenie MST z min_weight_match_g
                    Graph mst_with_mwmg = combine_mst_with_minweight_match_g(mst, min_weight_match_g); // byc moze do poprawy - wiecej debugow
                    // Krok 4b - Find Euler Cycle Path
                    List<Vertex> euler_path = find_euler_path(mst_with_mwmg);
                    // Krok 5 - Find TSP Cycle Path using Shortcut concept
                    List<Vertex> tsp_path = find_good_aprox_of_tsp(euler_path);
                    double distance = calculateDistance(tsp_path);
                    Console.WriteLine("Order of vertices:");
                    foreach (Vertex v in tsp_path)
                    {
                        Console.Write("<" + v.Position.X + "," + v.Position.Y + ">, ");
                    }
                    Console.WriteLine("distance: {0:0.0000}", distance);
            }
            catch (ArgumentException aex)
            {
                Console.WriteLine(aex.Message);
            }
        }
        /*
        private static void minimumWeightMatchingofOddVertex(AdjacencyMatrixGraph graph)
        {
            // Krok 1 - Find odd vertexes
            for (int i = 0; i < graph.VerticesCount; i++)
            {
               // graph
            }
            //throw new NotImplementedException();
        }


        private static void randomInitializationOfGraph(AdjacencyMatrixGraph graph)
        {
            Random rand = new Random(DateTime.Now.Millisecond);
            for (int i = 0; i < graph.VerticesCount; i++)
            {
                for (int j = i; j < graph.VerticesCount; j++)
                {
                    if (i == j)
                    {
                        graph.AddEdge(i, j, 0);
                    }
                    else
                    {
                        graph.AddEdge(i, j);
                    }
                }
            }
        }

        public static void show(IGraph g)
        {
            Console.WriteLine();
            for (int v = 0; v < g.VerticesCount; ++v)
            {
                Console.Write(" {0}: ", v);
                foreach (Edge e in g.OutEdges(v))
                    Console.Write("  {0}", e);
                Console.WriteLine();
            }
            Console.WriteLine();
        }*/
    }
}
